Cycle (graph theory)

In graph theory, the term cycle may refer to a closed path. If repeated vertices are allowed, it is more often called a closed walk. If the path is a simple path, with no repeated vertices or edges other than the starting and ending vertices, it may also be called a simple cycle, circuit, circle, or polygon; see Cycle graph. A cycle in a directed graph is called a directed cycle.

The term cycle may also refer to:

• An element of the binary or integral (or real, complex, etc.) cycle space of a graph. This is the usage closest to that in the rest of mathematics, in particular algebraic topology. Such a cycle may be called a binary cycle, integral cycle, etc.
• An edge set that has even degree at every vertex; also called an even edge set or, when taken together with its vertices, an even subgraph. This is equivalent to a binary cycle, since a binary cycle is the indicator function of an edge set of this type.

Chordless cycles in a graph are sometimes called graph holes. A graph antihole is the complement of a graph hole.

Cycle detection

A graph has a cycle if and only if depth-first search produces a back edge.^[1] This is true for both directed and undirected graphs. In the case of undirected graphs, only O(n) time is required, since at most n-1 edges can be tree edges (where n is the number of vertices). In the case of directed graphs, topological sorting algorithms will usually detect cycles too, since those are obstacles for topological order to exist.

See also

• Euler cycle
• Hamiltonian cycle
• Chordal graph

References